package Lee_code;

import java.util.Arrays;

public class Lee_518_dfs
{
    int sum;
    int count;
    int len;
    public int change(int amount, int[] coins) {
        count = 0;
        sum = amount;
        len = coins.length;
        Arrays.sort(coins);
        dfs(0, coins, 0);

        return count;

    }

    private void dfs(int cur_sum, int[] coins, int index) {
        if (cur_sum==sum)
        {
            count++;
            return;
        } else if (cur_sum>sum) {
            return;
        }

        for(int i=index; i<len; i++)
        {
            dfs(cur_sum+coins[i], coins, i);
        }
    }
}
